SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Jump-and-Walk algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Jump-and-Walk algorithm</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p><b>Jump-and-Walk</b> is an <a href="Algorithm" title="Algorithm">algorithm</a> for <a href="Point_location" title="Point location">point location</a> in <a href="Triangulation" title="Triangulation">triangulations</a> (though most of the theoretical analysis were performed in 2D and 3D random <a href="Delaunay_triangulation" title="Delaunay triangulation">Delaunay triangulations</a>). Surprisingly, the algorithm does not need any preprocessing or complex data structures except some simple representation of the triangulation itself. The predecessor of Jump-and-Walk was due to Lawson (1977) and Green and Sibson (1978), which picks a random starting point S and then walks from S toward the query point Q one triangle at a time. But no theoretical analysis was known for these predecessors until after mid-1990s.

</p><p>Jump-and-Walk picks a small group of sample points and starts the walk from the sample point which is the closest to Q until the simplex containing Q is found. The algorithm was a folklore in practice for some time, and the formal presentation of the algorithm and the analysis of its performance on 2D random Delaunay triangulation was done by Devroye, Mucke and Zhu in mid-1990s (the paper appeared in Algorithmica, 1998). The analysis on 3D random Delaunay triangulation was done by Mucke, Saias and Zhu (ACM Symposium of Computational Geometry, 1996). In both cases, a <a href="Boundary_value_problem" title="Boundary value problem">boundary condition</a> was assumed, namely, Q must be slightly away from the boundary of the convex domain where the vertices of the random Delaunay triangulation are drawn. In 2004, Devroye, Lemaire and Moreau showed that in 2D the boundary condition can be withdrawn (the paper appeared in Computational Geometry: Theory and Applications, 2004).

</p><p>Jump-and-Walk has been used in many famous software packages, e.g., QHULL, Triangle and <a href="CGAL" title="CGAL">CGAL</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGreenSibson1978" class="citation cs2">Green, P. J.; Sibson, R. (1978), "Computing Dirichlet tessellations in the plane", <i>The Computer Journal</i>, <b>21</b> (2): <span class="nowrap">168–</span>173, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fcomjnl%2F21.2.168">10.1093/comjnl/21.2.168</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0485467">0485467</a></cite>.</li>

<li><cite id="CITEREFLawson1977" class="citation cs2">Lawson, C. (1977), "Software for C1 surface interpolation", in <a href="John_R._Rice_(computer_scientist)" title="John R. Rice (computer scientist)">Rice, J. R.</a> (ed.), <i>Mathematical Software III</i>, NY: Academic Press, pp. <span class="nowrap">161–</span>194</cite>.</li>

<li><cite id="CITEREFDevroyeLemaireMoreau2004" class="citation cs2">Devroye, Luc; Lemaire, Christophe; Moreau, Jean-Michel (2004), "Expected time analysis for Delaunay point location", <i><a href="Computational_Geometry_(journal)" title="Computational Geometry (journal)">Computational Geometry: Theory and Applications</a></i>, <b>29</b> (2): <span class="nowrap">61–</span>89, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.comgeo.2004.02.002">10.1016/j.comgeo.2004.02.002</a></span>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2082208">2082208</a></cite>.</li>

<li><cite id="CITEREFDevroyeMückeZhu1998" class="citation cs2">Devroye, L.; Mücke, E. P.; Zhu, Binhai (1998), "A note on point location in Delaunay triangulations of random points", <i><a href="Algorithmica" title="Algorithmica">Algorithmica</a></i>, <b>22</b> (4): <span class="nowrap">477–</span>482, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.8612">10.1.1.15.8612</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FPL00009234">10.1007/PL00009234</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1701623">1701623</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3000041">3000041</a></cite>.</li>

<li><cite id="CITEREFMückeSaiasZhu1999" class="citation cs2">Mücke, Ernst P.; Saias, Isaac; Zhu, Binhai (1999), "Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations", Special issue for 12th ACM <a href="Symposium_on_Computational_Geometry" title="Symposium on Computational Geometry">Symposium on Computational Geometry</a> (Philadelphia, PA, 1996), <i><a href="Computational_Geometry_(journal)" title="Computational Geometry (journal)">Computational Geometry: Theory and Applications</a></i>, <b>12</b> (<span class="nowrap">1–</span>2): <span class="nowrap">63–</span>83, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0925-7721%2898%2900035-2">10.1016/S0925-7721(98)00035-2</a></span>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1677599">1677599</a></cite>.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-12" href="https://en.wikipedia.org/wiki/?title=Jump-and-Walk_algorithm&oldid=1289979449">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>